package Algorithm.bfs;

import java.util.*;

/**
 * 有障碍点的无界国际象棋
 * 题目简述：在一个无界棋盘中存在一些障碍点，马可走日，求从一个格子K走到另一个指定格子D的最少步数
 */
public class BoundlessChess {

    public static void main(String[] args) {
        System.out.println(findShortestStep(new Point(0,0), new Point(2,4), new HashSet<>()));
    }

    /**
     * 思路：广度优先遍历。由于棋盘是无界的，所以不能用深度遍历，只能用广度，
     * 一个节点的下一层节点即自己周边所能直接到达的八个节点，注意过滤已到达节点和障碍节点即可
     */
    static Deque<Point> deque = new ArrayDeque<>();
    static Set<Point> used = new HashSet<>();
    static Set<Point> obs;
    public static int findShortestStep(Point K, Point D, Set<Point> obstacles) {
        obs = obstacles;
        deque.add(K);
        int step = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 1;i <= size;i++) {
                Point p = deque.removeFirst();
                if (p.x == D.x && p.y == D.y) {
                    return step;
                }
                addDeque(p.x+1, p.y+2);
                addDeque(p.x+2, p.y+1);

                addDeque(p.x+1, p.y-2);
                addDeque(p.x+2, p.y-1);

                addDeque(p.x-1, p.y-2);
                addDeque(p.x-2, p.y-1);

                addDeque(p.x-1, p.y+2);
                addDeque(p.x-2, p.y+1);
            }
            step++;
        }
        return -1;
    }

    private static void addDeque(int x, int y) {
        Point p = new Point(x, y);
        if (!used.contains(p) && !obs.contains(p)) {
            deque.addLast(p);
            used.add(p);
        }
    }

    public static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}
